//二叉树中和为某一值的路径(二): https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
  public:
    void FindPathDFS(TreeNode* root, int expectNumber, vector<vector<int> >& result, vector<int>& list) 
    {
        if (root == nullptr) 
        {
            return;
        }
        //先添加值
        list.push_back(root->val);
        expectNumber -= root->val;
        //检测条件是否满足题面需求
        if (root->left == nullptr && root->right == nullptr && expectNumber == 0) 
        {
            result.push_back(list);
        }
        //dfs进去
        FindPathDFS(root->left, expectNumber, result, list);
        FindPathDFS(root->right, expectNumber, result, list);
        list.pop_back(); //回退
    }

    vector<vector<int> > FindPath(TreeNode* root, int expectNumber) 
    {
        vector<vector<int> > result;
        vector<int> list;
        FindPathDFS(root, expectNumber, result, list);
        return result;
    }
};